README.md

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true 

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

Solutions (Python)

1. Recursion

classTrie: def__init__(self, x=''): """ Initialize your data structure here. """self.val=xself.children= [] definsert(self, word: str) ->None: """ Inserts a word into the trie. """ifnotwordand''notin [child.valforchildinself.children]: self.children.append(Trie()) elifword: forchildinself.children: ifchild.val==word[0]: child.insert(word[1:]) returnNoneself.children.append(Trie(word[0])) self.children[-1].insert(word[1:]) defsearch(self, word: str) ->bool: """ Returns if the word is in the trie. """ifnotword: return''in [child.valforchildinself.children] forchildinself.children: ifchild.val==word[0]: returnchild.search(word[1:]) returnFalsedefstartsWith(self, prefix: str) ->bool: """ Returns if there is any word in the trie that starts with the given prefix. """ifnotprefix: returnTrueforchildinself.children: ifchild.val==prefix[0]: returnchild.startsWith(prefix[1:]) returnFalse# Your Trie object will be instantiated and called as such:# obj = Trie()# obj.insert(word)# param_2 = obj.search(word)# param_3 = obj.startsWith(prefix)